题目需要求的是这个式子:
由小学奥数知识可知:
所以上式等价于:
先看前部分,
递推求出 数组,做前缀和后与 相乘,记为
再将 数组求前缀和后得到第一部分答案。
再看后部分,
线性筛出约数个数后求两次前缀和即可。
时间复杂度 。
#include <cstdio>
#define Mod 998244353
const int MAXN = 1000000;
int t , l , r , k , d[ MAXN + 5 ] , num[ MAXN + 5 ] , prime[ MAXN + 5 ];
int inv[ MAXN + 5 ] , pre_inv[ MAXN + 5 ];
int fir[ MAXN + 5 ] , sec[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
d[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
d[ i ] = 2 , num[ i ] = 1;
}
for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) {
d[ i * prime[ j ] ] = d[ i ] / ( num[ i ] + 1 ) * ( num[ i ] + 2 );
num[ i * prime[ j ] ] = num[ i ] + 1;
break;
}
d[ i * prime[ j ] ] = d[ i ] * d[ prime[ j ] ];
num[ i * prime[ j ] ] = 1;
}
}
}
void Init( ) {
inv[ 0 ] = inv[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ )
inv[ i ] = 1ll * ( Mod - Mod / i ) * inv[ Mod % i ] % Mod;
for( int i = 1 ; i <= MAXN ; i ++ )
pre_inv[ i ] = ( pre_inv[ i - 1 ] + inv[ i ] ) % Mod;
for( int i = 1 ; i <= MAXN ; i ++ )
fir[ i ] = 1ll * i * pre_inv[ i ] % Mod;
for( int i = 1 ; i <= MAXN ; i ++ )
fir[ i ] = ( fir[ i - 1 ] + fir[ i ] ) % Mod;
sieve( );
for( int i = 1 ; i <= MAXN ; i ++ )
sec[ i ] = ( sec[ i - 1 ] + d[ i ] ) % Mod;
for( int i = 1 ; i <= MAXN ; i ++ )
sec[ i ] = ( sec[ i - 1 ] + sec[ i ] ) % Mod;
}
int main( ) {
Init( );
scanf("%d",&t);
while( t -- ) {
scanf("%d %d",&l,&r);
printf("%d\n", ( ( fir[ r ] - fir[ l - 1 ] + Mod ) % Mod - ( sec[ r ] - sec[ l - 1 ] + Mod ) % Mod + Mod ) % Mod );
}
return 0;
}